/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 5/28/2008
 */

#ifndef BTNODE_H
#define BTNODE_H

#include <vector>
#include "RecordFile.h"
#include "PageFile.h"

using namespace std;
// class keyandrid used to store information inside leaf nodes
// buffer by itself is pretty raw so we want to further format information inside
// buffer to be (recid, key) pairs 
class keyandrid {
public:
	int key;
	//RecordId recid;
    PageId krpid;
    int krsid;
	// bool operator<(keyandrid rhs) { return key < rhs.key; }
};

struct sorting {
  bool operator() (const keyandrid &a, const keyandrid &b) { return (a.key<b.key); }
};

/**
 * BTLeafNode: The class representing a B+tree leaf node.
 */
class BTLeafNode {
  public:
   /**
    * Insert the (key, rid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param rid[IN] the RecordId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, const RecordId& rid);

   /**
    * Insert the (key, rid) pair to the node
    * and split the node half and half with sibling.
    * The first key of the sibling node is returned in siblingKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert.
    * @param rid[IN] the RecordId to insert.
    * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
    * @param siblingKey[OUT] the first key in the sibling node after split.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey);

   /**
    * Find the index entry whose key value is larger than or equal to searchKey
    * and output the eid (entry id) whose key value &gt;= searchKey.
    * Remember that keys inside a B+tree node are sorted.
    * @param searchKey[IN] the key to search for.
    * @param eid[OUT] the entry number that contains a key larger              
    *                 than or equalty to searchKey.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locate(int searchKey, int& eid);

   /**
    * Read the (key, rid) pair from the eid entry.
    * @param eid[IN] the entry number to read the (key, rid) pair from
    * @param key[OUT] the key from the slot
    * @param rid[OUT] the RecordId from the slot
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC readEntry(int eid, int& key, RecordId& rid);

   /**
    * Return the pid of the next slibling node.
    * @return the PageId of the next sibling node 
    */
    PageId getNextNodePtr();


   /**
    * Set the next slibling node PageId.
    * @param pid[IN] the PageId of the next sibling node 
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC setNextNodePtr(PageId pid);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount();
 
   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);
	
	void initbuffer(); // not really useful since we nvr read past a certain limit
    // but might be used by higher level users

	// function below places all the information inside buffer into vector keyandrid
	void buftovec();

	// function below places all information from vector keyandrid into buffer
	void vectobuf();
	
	// sort predicate for vector keyrid
	// bool keyandridSort(const keyandrid & d1, const keyandrid & d2);

    void setecount(int ec); // sets ecount of leafnode

    // since PageFile::PAGE_SIZE == 1024 meaning 1024 bytes since 1 char == 1 byte
    // then 1024/4 = 256 if using int
    int buffer[256];
    // note that recordid consists of 2 int types called pid and sid while key is just an int
    vector<keyandrid> keyrid; // datastructure to store recordid and key
    void setmaxentrynum(int mxn); // sets the max entry num to buffer[3]

    void sortVector(); // our vector sorting function

    void setvalues(int ec, /*PageId curpid,*/ int m_ent_num, PageId rpid, int hoft, int type, int next);

    void incr_heightoftree();

    int gethasnext();
private:
   /**
    * The main memory buffer for loading the content of the disk page 
    * that contains the node.
    */
    // char buffer[PageFile::PAGE_SIZE];
	
	// PageId currnode; // this is the current node number (unused)
	// PageId eofnode; // stores the endPid() result so we know where file ends (unused)
	int ecount; // this stores the number of entries (rid, key) in the pagefile
	//bool empty; // true if pagefile is empty
	PageId nxtndeptr; // where we get information for the next pageid
    // PageId curr_pid; // current node's pid
	int maxentrynum; // this is 82 from 248/3 
	PageId root_pid; // root's pid
    int height_of_tree; // tree height
    int node_type; // 0 for non-leaf and root, 1 for leafnode
    int hasnext; // 0 for no (last pageid), 1 for has active ptr to next
	// 256 spaces in buffer available for use
	// 3 spaces for rid & key value pairs
	// 1st value in buffer is for ecount: buffer[0]
	// 2nd value is for the next pageid: buffer[1]
	// 3rd value holds the current node's padeid: buffer[2] (unused)
	// 4th value max number of possible entries, maxentrynum: buffer[3]
    // 5rd value holds the root node's padeid: buffer[4] 
    // 6th value holds the height of tree: buffer[5]  
    // 7rd value holds the current node's type: buffer[6] 
    // 8rd value holds if node has a working next field: buffer[7] 
    // we leave buffer[8] and buffer[9] free for whatever future usage
}; 


/**
 * BTNonLeafNode: The class representing a B+tree nonleaf node.
 */
class BTNonLeafNode {
  public:
   /**
    * Insert a (key, pid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, PageId pid);

   /**
    * Insert the (key, pid) pair to the node
    * and split the node half and half with sibling.
    * The sibling node MUST be empty when this function is called.
    * The middle key after the split is returned in midKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
    * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey);

   /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * Remember that the keys inside a B+tree node are sorted.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locateChildPtr(int searchKey, PageId& pid);

   /**
    * Initialize the root node with (pid1, key, pid2).
    * @param pid1[IN] the first PageId to insert
    * @param key[IN] the key that should be inserted between the two PageIds
    * @param pid2[IN] the PageId to insert behind the key
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC initializeRoot(PageId pid1, int key, PageId pid2);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount();

   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);

    // non-leaf node contains key and pageid separately 
    int buffer[256];
    int tmpbuffer[258]; // used only in insertandsplit

    void insertKeyPid(int key, PageId pid, int index);
    void insertKeyPid_tmp(int key, PageId pid, int index);
    void buf_to_tmpbuf();

    // function below sets values of buffer (used for insertandsplit)
    void setvalues(int kc, int pc, int mkc, int mpc, int s_used, int type);
  private:
   /**
    * The main memory buffer for loading the content of the disk page 
    * that contains the node.
    */
    // char buffer[PageFile::PAGE_SIZE];
	
	int keycount; // number of keys in a nonleafnode
	int pidcount; // number of pids in a nonleafnode
	// PageId nxtndeptr; // hold the next node's pageid
	// PageId currnlnode; // holds the pageid of the current non-leaf node
	int maxkeycount; // holds the maximum number of keys for a non-leaf node
	int maxpidcount; // holds the maximum number of pids for a non-leaf node
    int spaceused; // how many spaces in the 256 used up
    // buffer[5] unused
	int node_type; 
	// 256 spaces in buffer available for use
	// 1 space each for pageid and key
	// 1st value in buffer is for keycount: buffer[0]
	// 2nd value is for pidcount: buffer[1]
	// 3rd value holds the maxkeycount: buffer[2] 
	// 4th value holds the maxpidcount: buffer[3]
    // 5th value holds space used so far: buffer[4] 
    // 6th value buffer[5] (unused)
    // 7th value (deliberately the same as leafnode) check type: buffer[6]
    // doing this so we have odd number of spaces
    // 256 - 7 = 249, we will have 
    // n keys and n+1 pageids
    // 124 keys and 125 pageids
    // pageids starting at buffer[7]-buffer[255]
    // keys starting at buffer[8]-buffer[254]
}; 

#endif /* BTNODE_H */
